// https://www.lintcode.com/problem/course-schedule/description

class Solution {
public:
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
    
    // 拓扑排序，入度为0的课就可以修
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        map<int, int> rec;
        // [[5,8],[3,5],[1,9],[4,5],[0,2],[1,9],[7,8],[4,9]] 要用multiset，还有这种奇怪的例子出现
        // vector<set<int>> edges(numCourses);
        vector<multiset<int>> edges(numCourses);
        queue<int> q;
        int node = 0;
        for (auto it: prerequisites)
        {
            edges[it.second].insert(it.first); 
            // rec[it.second]++;
            rec[it.first]++; //入度
        }
        for (int i = 0; i < numCourses; ++i)
        {
            if (rec.find(i) == rec.end())
            {
                q.push(i);
            }
        }
        while (!q.empty())
        {
            int tmp = q.front();
            q.pop();
            node++;
            for (auto it = edges[tmp].begin(); it != edges[tmp].end(); ++it)
            {
                rec[*it]--;     
                if (rec[*it] == 0)
                    q.push(*it);
            }
        }
        return node == numCourses;
    }
};